﻿#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <set>

using namespace std;


//set底层是⽤红⿊树实现，增删查效率是 ，迭代器遍历是⾛的搜索树的中序，所以是有序
//的。
//int main()
//{
//	set<int> s;
//	// 去重+降序排序（给⼀个⼤于的仿函数）
//	//set<int, greater<int>> s;
//	s.insert(5);
//	s.insert(2);
//	s.insert(7);
//	s.insert(5);
//
//	//set<int>::iterator it = s.begin();
//	//set迭代器是⼀个双向迭代器
//	auto it = s.begin();
//	while (it != s.end())
//	{
//		// error C3892: “it”: 不能给常量赋值
//      //set的iterator和const_iterator都不⽀持迭代器修改数据，修改关键字数据，破坏了底层搜索树的结构。
//		// *it = 1;
//		cout << *it << " ";
//		++it;
//	}
//	cout << endl;
//
//	// 插⼊⼀段initializer_list列表值，已经存在的值插⼊失败
//	s.insert({ 2,8,3,9 });
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	set<string> strset = { "sort", "insert", "add" };
//	// 遍历string⽐较ascll码⼤⼩顺序遍历的
//	for (auto& e : strset)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	return 0;
//}

//int main()
//{
//	set<int> s = { 4,2,7,2,8,5,9 };
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	// 删除最⼩值
//	s.erase(s.begin());
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	// 直接删除x
//	int x;
//	cin >> x;
//	int num = s.erase(x);//x不存在返回0，存在返回1
//	if (num == 0)
//	{
//		cout << x << "不存在！" << endl;
//	}
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	// 直接查找再利⽤迭代器删除x
//	cin >> x;
//	auto pos = s.find(x);
//	if (pos != s.end())
//	{
//		s.erase(pos);
//	}
//	else
//	{
//		cout << x << "不存在！" << endl;
//	}
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	// 算法库的查找 O(N)
//	auto pos1 = find(s.begin(), s.end(), x);
//
//	// set⾃⾝实现的查找 O(logN)
//	auto pos2 = s.find(x);
//
//	// 利⽤count间接实现快速查找
//	cin >> x;
//	if (s.count(x))
//	{
//		cout << x << "在！" << endl;
//	}
//	else
//	{
//	    cout << x << "不存在！" << endl;
//	}
//	return 0;
//}

//int main()
//{
//	set<int> myset;
//	for (int i = 1; i < 10; i++)
//		myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90
//
//	for (auto e : myset)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	// 返回⼤于等于val位置的迭代器
//	//iterator lower_bound(const value_type & val) const;
//	// 
//	// 返回⼤于val位置的迭代器
//	//iterator upper_bound(const value_type & val) const;
//	// 
//	//// 实现查找到的[itlow,itup)包含[30, 60]区间
//	//// 返回 >= 30
//	//auto itlow = myset.lower_bound(30);
//
//	//// 返回 > 60
//	//auto itup = myset.upper_bound(60);//迭代器给到70的位置
//
//	//>=25
//	auto itlow = myset.lower_bound(25);//给到30的位置
//	//>55
//	auto itup = myset.upper_bound(55);//给到60的位置
//
//	// 删除这段区间的值
//	myset.erase(itlow, itup);
//	for (auto e : myset)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	return 0;
//}

int main()
{
	// 相⽐set不同的是，multiset是排序，但是不去重
	multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 };

	auto it = s.begin();

	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	int x;
	cin >> x;
	// 相⽐set不同的是，x可能会存在多个，find查找中序的第⼀个
	//这样的好处是，找到第一个，迭代器就可以根据中序遍历找到后续的x
	auto pos = s.find(x);
	while (pos != s.end() && *pos == x)
	{
		cout << *pos << " ";
		++pos;
	}
	cout << endl;

	// 相⽐set不同的是，count会返回x的实际个数
	cout << s.count(x) << endl;

	// 相⽐set不同的是，erase给值时会删除所有的x
	s.erase(x);
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	return 0;
}